package com.zjsru.plan2025.oneday;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 922. 按奇偶排序数组 II
 *
 * @Author: cookLee
 * @Date: 2025-02-04
 */
public class SortArrayByParityII {
    /**
     * 主
     * \
     * 输入：nums = [4,2,5,7]
     * 输出：[4,5,2,7]
     * 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
     * \
     * 输入：nums = [2,3]
     * 输出：[2,3]
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        SortArrayByParityII sortArrayByParityII = new SortArrayByParityII();
        int[] nums = new int[]{4, 2, 5, 7};
        System.out.println(Arrays.toString(sortArrayByParityII.sortArrayByParityII(nums)));
    }

    /**
     * 按奇偶校验对数组进行排序ii
     *
     * @param nums nums
     * @return {@link int[]}
     */
    public int[] sortArrayByParityII(int[] nums) {
        int[] result = new int[nums.length];
        Queue<Integer> oddQueue = new PriorityQueue<>();
        Queue<Integer> evenQueue = new PriorityQueue<>();
        for (int num : nums) {
            if (num % 2 == 0) {
                evenQueue.add(num);
            } else {
                oddQueue.add(num);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                result[i] = evenQueue.poll();
            } else {
                result[i] = oddQueue.poll();
            }
        }
        return result;
    }

    public int[] sortArrayByParityII2(int[] nums) {
        int n = nums.length;
        int j = 1;
        for (int i = 0; i < n; i += 2) {
            if ((nums[i] & 1) != 0) {
                while ((nums[j] & 1) != 0) {
                    j += 2;
                }
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
            }
        }
        return nums;
    }
}
